package practice.sort;

/**
 * 归并排序
 */
public class MergeSort extends SortAdaptor {
    private static int[] aux;

    public static void main(String[] args) {
        int[] nums = {3, 9, 10, 2, 3, 123, 239, 4, 13, 443, 23, 29};
        sortBU(nums);
        for (int num :
                nums) {
            System.out.print(num + " ");
        }
    }

    /**
     * 自顶向下归并排序Top-Down
     *
     * @param nums
     */
    public static void sortTD(int[] nums) {
        if (nums.length <= 1) {
            return;
        }
        aux = new int[nums.length];
        sortTD(nums, 0, nums.length - 1);
    }

    private static void sortTD(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        sortTD(nums, left, mid);
        sortTD(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    /**
     * 自底向上归并，bottom-up
     *
     * @param nums
     */
    private static void sortBU(int[] nums) {
        if (nums.length <= 1) {
            return;
        }
        aux = new int[nums.length];
        //i 子数组的大小，从1开始
        for (int i = 1; i < nums.length; i *= 2) {
            //j 子数组的起始索引，每次增加2倍子数组大小，使其指向下一组需要归并的子数组的开始
            for (int j = 0; j < nums.length - i; j += 2 * i) {
                //中间数，左指针加子数组大小减1
                int mid = j + i - 1;
                //右指针，左指针加2倍子数组大小减1
                int right = j + i * 2 - 1;
                merge(nums, j, mid, right < nums.length - 1 ? right : nums.length - 1);
            }
        }

    }

    /**
     * 归并方法，将部分有序的子数组（left,mid)(mid+1,right)合并成一个有序的数组(left,right)
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     */
    private static void merge(int[] nums, int left, int mid, int right) {
        if (nums[mid] < nums[mid + 1]) {
            return;
        }
        //左右数组的指针
        int i = left, j = mid + 1;
        //复制元素到辅助数组
        for (int k = left; k <= right; k++) {
            aux[k] = nums[k];
        }
        //将数组有序排列
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                //左半边数组已经用尽，取右半边数据
                nums[k] = aux[j++];
            } else if (j > right) {
                //右半边数组已经用尽，取左半边数据
                nums[k] = aux[i++];
            } else if (aux[i] < aux[j]) {
                //左边数组的当前数小于右边的，取左边数
                nums[k] = aux[i++];
            } else {
                //左边数组的当前数大于右边的，取右边数
                nums[k] = aux[j++];
            }
        }
    }
}
